00100		     COMPUTER PERCEPTION OF VISUAL SCENES
00105				   by
00110	             Thomas O. Binford, Stanford University    and
00115	             Jay M. Tenenbaum,  Stanford Research Institute
00120	
00200	
00202	Introduction.
00205	Computer perception is studied for its obvious practical applications
00210	and for the insights it provides into complex system organization and the   
00215	nature of human and artificial intelligence.
00225	In constructing machines that see, we seek answers to a broad range of 
00230	questions: How should the system be partitioned functionally?
00500	What control structure is needed?
00600	What  are  inherent  computational  limits,  in
00700	interconnections for  parallel  machines;  in  computation  time  for
00800	serial  machines?  
00805	Many of the problems encountered are widespread in intelligence:
01000	How is knowledge represented? How is it
01100	integrated in the system? How does it guide  in  drawing  conclusions
01200	from  image  data? How does knowledge interact with conclusions drawn
01300	from the image? Given a system, what can it see?  What  is  necessary
01400	for visual learning? What are given systems capable of learning? Many
01500	results cannot be taken literally as models  for  biological  systems
01600	because  of  differences  in  hardware and gaps in our knowledge, but
01700	fundamental limitations are shared, and many examples are applicable.
01800	The research may occasionally borrow from biology, but we cannot copy
01900	nature,  since  the  details  are  not  known  and  the  hardware  is
02000	different.
02100	
02200	Issues that arise in mechanizing perception also arise in many
02205	other areas of artificial intelligence and computer science.
02300	Visualization  is  an   important   part   of   problem-solving   and
02400	mathematics.  Graphs  and  visual  displays  are an vital to 
02500	communication.  Representation  of   knowledge   and   its   use   in
02600	goal-directed  ways  are  universal  problems in intelligence. For example,
02700	representations  of shape are important in augmenting  productivity  and  
02800	man-machine  communication.  
02805	
02810	The use of computer  graphics  and  design
02900	automation is  already  common  in  industry.  The information already
02905	available from these design processes can be used by computers to
03000	aid  in controlling parts and
03100	material flow, in designing transport systems, in extending modularity  and
03200	commonality  of  parts  and  procedures,and in 
03300	sensing and scheduling production.
03400	These abilities which require some of the most sophisticated A.I. techniques
03500	will have a profound effect on near term productivity. 
03900	
04000	Industry   uses   hundreds   of   industrial  robots,  some  computer
04100	controlled. Touch and simple vision can incrementally  improve  these
04200	robots  which  now have no sensing and thus no contingency actions. 
04205	Sensor equipped robots coupled to mini-computers will be able to 
04210	sense color and strong brightness contrasts, recognize known objects from 
04215	two dimensional outlines (e.g., the top view of a flat object) or 
04220	three dimensionally, by determining depth.  With these skills, they will
04225	be able to align mating parts in assembly operations, increase reliability
04230	by self-calibration, detect flaws and disasters, and permit large tolerances
04235	in parts transfer, even permitting parts to be taken from a bin.
04900	
05000	
05300	We  are interested in visual systems for function of an organism such
05400	as a robot that must manipulate or avoid objects rather than just  classifying
05500	them.  Manipulation requires three-dimensional interpretations and spatial
05600	relations of objects. Certain techniques  have  evolved  for  simpler
05700	problems;  e.g.  template matching or vector space classification for
05800	character recognition. It seems attractive to simply save  images  or
05900	feature  vectors,  then match against a scene or part of a scene. But
06000	objects occlude one another, parts have joints which move separately,
06100	there  are  many viewpoints, many possible objects, and many combinations
06200	of objects. Object classes are often defined by function, not shape (eg. coffee cups).
06300	Complex deductions are necessary to obtain spatial relations from an image.
06305	Finally, we must frequently deal with new
06400	objects. Direct template matching techniques are impractical for these requirements,      
06500	except in very carefully controlled applications.
     

00100	ELEMENTS OF A VISUAL SYSTEM
00200	
00300	The computer eye is some form of tv camera with color filters and a
00400	turret or zoom lens for closeup views.  The computer controls filters,
00500	lens and other parameters to optimize the image for each task [Tenenbaum].
00600	Sensor systems have inadequate dynamic range but system design studies
00700	suggest better compromises [Binford].  Humans use depth information
00800	obtained from stereo and motion parallax.  Several depth sensors
00900	based on triangulation have been built [Agin, Shirai, Munson].
01000	Range information with color should greatly simplify interpretation of
01100	scenes.
01200	
01300	The image is read into memory as an array of brightness values 
01400	(typically 300x300) with 4-8 bits for each sample for each color.
01500	The process of interpreting this mass of numbers into a symbolic
01600	description can be thought of as subdivided into segmentation,
01700	representation, and interpretation.
01800	
01900	The process of segmentation of a scene partitions it into meaningful entities
02000	which may be recognizable.  Segmentation in character recognition
02100	is simple since printed characters are clearly separated and
02200	labelled by black on white.
02300	It is harder to segment objects in a real scene (even simple scenes)
02400	because there are many possible properties for segmentation:
02500	uniformity of brightness, color, texture (itself a complex descriptor),
02600	regularity of boundaries, contiguity of depth (given stereo or other
02700	depth measurements).  Segmentation may also depend on depth cues from
02800	interpretation of texture gradients and occlusion.
02900	
03000	In what form do we represent objects internally in the computer?  The
03100	simplest form is a pictorial template, an array of brightness values
03200	to be matched directly against fragments of scenes by correlation.
03300	Given the inadequacies of this representation, we must describe
03400	partitioned regions symbolically in terms of extracted features like
03500	color, size, texture, and shape.  All these properties are inferred
03600	by complex processes from the image.  Simple descriptors for shape or
03700	texture may be used in simple tasks and limited context.  Shape might
03800	be described by the  ratio of the squared perimeter to the area of
03900	a region.  More sophisticated shape representations, needed for a wider
04000	range of tasks, are described later.
04100	
04200	Interpretation is often expressed as computing a distance measure between an
04300	object and a stored model.  For simple cases that can be useful.  When
04400	objects are occluded, there must be a partial match.  When objects are
04500	not identical, judgments of similarity depend on representation of
04600	shape and representation of the task, in order to define important
04700	differences.  The most useful approach is to build up symbolic
04800	descriptions and make symbolic descriptions of differences.  Sometimes,
04900	there are few enough models that matching with each model is possible.
05000	More generally, interpretation must make use of a large visual memory.
05100	
05200	Because of the evident interconnection of these three processes, one
05300	cannot proceed sequentially through segmentation, representation and interpretation
05400	and expect to obtain a globally consistent interpretation for all objects
05500	in a scene.  
     

00100	BLOCKS WORLD
00200	
00300	Research concentrated initially on scenes  of  blocks  as  a  simpler
00400	subproblem.  Roberts important work opened the field []. Objects were
00500	represented as built up of primitive parts, a block, a wedge,  and  a
00600	hexagonal  prism.   Primitives  were represented by their vertices in
00700	three dimensions. The program assumed it would first  obtain  perfect
00800	line  drawings.   It  attempted to identify unobscured polygons, then
00900	match sets of vertices to topologically  equivalent  model  vertices.
01000	Recognition  meant  finding  a three-dimensional model which could be
01100	translated, rotated, and scaled, then projected to match part of  the
01200	image.   The  recognized  piece  was  then cut away and the remainder
01300	considered. Some segmentation was performed with the recognition.
01400	
01500	That organization has proven inadequate. It  is  not  enough  to  use
01600	models  and template matching. Producing perfect line drawings is not
01700	practical. Some lines are missed. Shadows,  reflections  and  surface
01800	markings  cause  extra lines. Errors made at one stage are compounded
01900	by later stages.
02000	
02100	Guzman found  heuristics  to  segment  complex  scenes  into  objects
02200	without  template  matching.   The program linked regions at vertices
02300	with three lines if they  were  not  a  T,  between  regions  without
02400	concavities  (internal  angle less than pi) at the vertex. See figure
02500	1a. Eventually he required almost the same condition at both ends  of
02600	a  line  before  linking  (except that T was allowed at one end). See
02700	figure 1b. We have rephrased his  conditions  for  clarity.   Regions
02800	linked  twice  were  joined  into clusters; regions linked twice to a
02900	cluster were also joined. Other links were  introduced  without  much
03000	motivation.  The program did surprisingly well, but had problems with
03100	holes and other non-convexities, and with accidental  alignment.   It
03200	depended  on  being  told  the  background.  These techniques did not
03300	extend far. Falk joined lines into edges  of  bodies;  since  missing
03400	edges cause regions to be non-planar, some errors could be avoided.
03500	
03600	Huffman   and   Clowes  []  analyzed  trihedral  vertices  seen  from
03700	non-singular perspective (small change of viewpoint leaves the number
03800	of  visible  lines unchanged) by classifying edges as convex, concave
03900	and obscuring. It was possible to reject some drawings as  impossible
04000	under  these  assumptions.  Waltz expanded that labelling of lines to
04100	include cracks, shadows, and illumination. It would  seem  that  such
04200	large  numbers  of  possible  interpretations  would  be unmanagable;
04300	instead,  the  increased  precision  of  descriptions  allows   rapid
04400	discarding of wrong interpretations. Not only are solutions possible,
04500	they are quickly obtained. In considering possible solutions,
04600	
04700	
04800	
04900	
05000	
05100	The best performance  in  segmenting  image  data  is  given  by  the
05200	Binford-Horn  []  line finder and the Shirai [] line finder.  The two
05300	are complementary and should be combined.  The former is able to find
05400	most  lines  in  a  scene  of  white  blocks on a white background in
05500	arbitrary lighting.  It  misses  a  few  lines  which  are  found  by
05600	subsequent  prediction  and  verification  and garbles some vertices.
05700	Shirai's system performs much better.   It  requires  large  contrast
05800	with background however (white on black), and finds only features and
05900	objects for which cues are available from context.
06000	
06100	It is interesting  to  compare  these  systems  with  the  biological
06200	system.  Directional  edge  operators  are  scanned  over  the  image
06300	[Binford, Hueckel]; these compare  with  the  Hubel-Wiesel  cells  in
06400	higher  animals.   In  practice,  large  gradients at reflections and
06500	curved surfaces cause masses of spurious edge fragments.  These  were
06600	eliminated  by  subtracting  the  local  average  at each point, thus
06700	subtracting out smooth gradients [Binford].  This process is familiar
06800	as lateral inhibition in the retina of animals.
06900	
07000	The  Binford-Horn  program  used an optimal curve sequential decision
07100	process to extend curves and test at each extension, whether to keep,
07200	terminate,  or  extend further.  Shirai began with white objects on a
07300	black background; context was used at each step to decide what to  do
07400	next.   At  vertices,  the  extension  of  boundary lines was tested.
07500	Completions for unterminated  lines  was  searched  for.   Additional
07600	lines  were  tested for at vertices, including some parallel to lines
07700	at adjacent vertices.  The  use  of  context  involved  not  changing
07800	thresholds,  but  using  special-purpose  operators: verify a line at
07900	known position and angle; find a line through a vertex.
08000	
     

00100	REAL WORLD VISION
00200	
00300	Studies for agricultural and earth resources surveys have  considered
00400	texture as a two-dimensional problem.  Bajcsy [] has analyzed outdoor
00500	scenes for which perspective and  three-dimensional  description  are
00600	important.   Textures were described by structures of texture elements with spatial
00700	relations.  Descriptors  for  texture  elements  and  relations  were
00800	obtained  from  the  Fourier  transform  for directionality (if any),
00900	size, contrast, and spacing of texture elements. The Fourier  transform
01000	was   found troublesome,however.   Color  and  texture  regions  were
01100	obtained.  Some  depth  relations  could  be  observed  from  texture
01200	gradient.   An  attempt was made to obtain consistent interpretations
01300	by first confirming  region  boundaries  by  independent  properties,
01400	making  three-dimensional  interpretations, and matching region descriptors with
01500	those of sky, trees, grass, etc. in a world model.
01600	
01700	quality of interpretation was limited by unreliability of region-growing process.
01800	Further work in outdoor  scenes attempts to  incorporate  the  world  model  and
01900	interpretation into the region growing process.
02000	  An interpretation of
02100	image regions  as  sky,  trees,  etc.  is  evaluated  by  calculating
02200	probabilities  for  consistency  of  object descriptions and boundary
02300	description.    Consistent   interpretations   which   maximize   the
02400	probabilistic evaluation are sought.
02500	
02600	Regions are merged  not only because of similarity of properties, but
02700	because
02800	the consistency of semantic interpretation 
02900	is improved.
     

00100	Conclusion.
00200	Visual perception by computer is a challenging but rewarding goal.
00300	Recently, several laboratories have begun to apply techniques
00400	from perception research to practical industrial tasks.
00500	General Motors laboratories has succeeded in mounting a wheel on 
00600	an axle. Stanford Research Institute and Hitachi Ltd. have each
00700	demonstrated systems which can distinguish sheet metal parts
00800	on a moving conveyor belt and determine their orientation to enable
00900	manipulation. Template matching techniques were used to take 
01000	advantage of the two dimensional nature of these tasks. Moreover,
01100	the conveyor demonstrations relied on the contrast between shiny metalic parts 
01200	and the black belt to simplify segmentation. Many industrial processes 
01300	share similar constraints or can be readily redesigned to do so.
01400	We thus expect a proliferation of industrial applications of 
01500	computer perception in the near future.